package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

/**
 * @author zhangjy
 * @description 删除二叉搜索树中的节点
 * @date 2025/4/27 10:01
 */
public class DeleteNode_450 {

    /**
     * 参考dmsxl：dfs-递归-不分遍历顺序
     * <p>
     * 分析：
     * 1.先找到待删除节点；
     * 2.开始删除节点，涉及节点移动，保证删除后还是BST
     * <p>
     * 思路：当待删除节点node的右孩子非空，让右孩子继位，即node的父节点parent，指向node.right；
     * 找不到：一种情况，直接返回null；
     * 找得到：4种情况；
     * 1）左、右孩子都空；
     * 2）左不空，右空；
     * 3）左空，右不空；
     * 4）左、右都不空——最复杂。
     * <p>
     * 为什么要返回新的节点？
     * ——因为，删除时，已经做了节点移动操作，返回的是删除后新的孩子节点；所以后面要重新设置对应孩子节点。
     */
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;

        // 找到后，开始删除
        if (root.val == key) {
            if (root.left == null && root.right == null) {
                return null;
            } else if (root.left != null && root.right == null) {
                return root.left;
            } else if (root.left == null && root.right != null) {
                return root.right;
            } else {
                // 左右都非空
                // 找到待删除节点root右孩子的最左节点（可能不是叶子节点），然后把root.left移动到最左叶子节点，这样就能保证BST特性
                TreeNode right = root.right;
                while (right.left != null) {
                    right = right.left;
                }
                right.left = root.left;
                return root.right;
            }
        }

        // 左
        root.left = deleteNode(root.left, key);
        // 右
        root.right = deleteNode(root.right, key);

        return root;
    }

}
